Date: Tue, 14 Jan 1997 23:29:46 GMT
Server: NCSA/1.5.1
Last-modified: Fri, 06 Sep 1996 13:33:17 GMT
Content-type: text/html
Content-length: 12302

<HTML><HEAD>
<title>CIRCA</title>
</HEAD>


<BODY>

<H1>CIRCA...</H1>

is an architecture for combining artificial intelligence and
real-time systems to achieve intelligent real-time control,
particularly of physical (robotic, manufacturing, aviation)
systems.  The research is conducted jointly between the
<!WA0><A HREF="http://ai.eecs.umich.edu/">Artificial Intelligence 
Laboratory</A> and the <!WA1><A HREF="http://www.eecs.umich.edu:80/RTCL/">Real
Time Computing Laboratory</A> <P>

<H1>Personnel</H1>

<!WA2><A HREF="http://ai.eecs.umich.edu/people/durfee/durfee.html">Edmund
H. Durfee, Associate Professor of EECS</A> <P>

<!WA3><A HREF="http://www.eecs.umich.edu:80/RTCL/kgshin/index.html">Kang
G. Shin, Professor of EECS</A> <P>

<!WA4><A HREF="http://ai.eecs.umich.edu/people/marbles/homepage.html">Ella
Atkins, Graduate Student</A> <P>

<!WA5><A HREF="http://www-personal.umich.edu/~mcvey/">Chip
McVey, Graduate Student</A> <P>

<H2>Alumni</H2>

<!WA6><A HREF="http://www.cs.umd.edu/users/musliner/index.html">David
J. Musliner</A>, PhD, now at Honeywell Technology Center <P>

<A>Eric Miller, MS, now at Loral.</A>

<H2>Some Publications</H2>

E. M. Atkins, E. H. Durfee, K. G. Shin, <!WA7><A HREF="http://ai.eecs.umich.edu/people/marbles/prob_paper.html">Plan Development Using Local Probabilistic Models</A>, Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence, pp. 49-56, August 1996.
<p>

E. M. Atkins, E. H. Durfee, K. G. Shin, <!WA8><A HREF="http://ai.eecs.umich.edu/people/marbles/papers/unhandled.abs.ps">Expecting the Unexpected:  Detecting and Reacting to Unplanned-for World States</A>, Proceedings of AAAI-96, pp. ????, August 1996.   (student abstract)
<p>

E. M. Atkins, E. H. Durfee, K. G. Shin, <!WA9><A HREF="http://ai.eecs.umich.edu/people/marbles/papers/action.workshop.ps">Detecting and Reacting to Unplanned-for World States</A>, AAAI-96 Workshop on Theories of Action, Planning, and Robot Control:  Bridging the Gap, pp. 7-14, August 1996.
<p>

E. M. Atkins, E. H. Durfee, K. G. Shin, <!WA10><A HREF="http://ai.eecs.umich.edu/people/marbles/papers/temporal.workshop.ps">Building a Plan with Real-Time Execution Guarantees</A>, AAAI-96 Workshop on Structural Issues in Planning and Temporal Reasoning, pp. 1-6, August 1996.
<p>

E. M. Atkins, E. H. Durfee, K. G. Shin, <!WA11><A HREF="http://ai.eecs.umich.edu/people/marbles/papers/plan.exec.symp.ps">Detecting and Reacting to Unplanned-for World States</A>, to appear in AAAI-96 Fall Symposium on Plan Execution:  Problems and Issues Technical Report, November 1996.
<p>

E. M. Atkins, E. H. Durfee, K. G. Shin, <!WA12><A HREF="http://ai.eecs.umich.edu/people/marbles/papers/flex.comp.symp.ps">Achieving Fully-Automated Aircraft Flight with Limited Resources</A>, to appear in AAAI-96 Fall Symposium on Flexible Computation in Intelligent Systems:  Results, Issues, and Opportunities Technical Report, November 1996.
<p>

D. J. Musliner, J. A. Hendler, A. K. Agrawala, E. H. Durfee,
J. K. Strosnider, and C. J. Paul,
<!WA13><a HREF="http://www.cs.umd.edu/users/musliner/papers/rtai.ps">
The Challenges of Real-Time AI</a>,
<i>IEEE Computer</i>, Vol 28 #1, January 1995.
Also appears as University of Maryland Technical Report CS-TR-3290
(UMIACS-TR-94-69).
<p>

D. J. Musliner,
<!WA14><a HREF="http://www.cs.umd.edu/users/musliner/papers/salsa.ps"> 
Using Abstraction and Nondeterminism to Plan Reaction Loops</a>,
<i>Proc. National Conf. on AI</i>, pp. 1036-1041, Seattle WA, August 1994.
<p>


D. J. Musliner,
<!WA15><a HREF="http://www.cs.umd.edu/users/musliner/papers/cirffss94.ps"> 
Predictive Sufficiency and the Use of Stored Internal State</a>,
in <i>Proc. Conf. on Intelligent Robotics in Field, Factory, Service, 
and Space</i>, pp. 298-305, Houston TX, March 1994.
<p>

D. J. Musliner, E. H. Durfee, and K. G. Shin,
<!WA16><a HREF="http://www.cs.umd.edu/users/musliner/papers/musliner-aij.ps"> 
World Modeling for the Dynamic Construction of Real-Time Control Plans</a>,
to appear in <i>AI Journal</i>, 1994.
<p>

D. J. Musliner, K. G. Shin, and E. H. Durfee,
<!WA17><a HREF="http://www.cs.umd.edu/users/musliner/papers/airtc94.ps"> 
Automating the Design of Real-Time Reactive Systems</a>,
in <i>Proc. Symposium on AI in Real-Time Control</i>, 1994.
<p>

D. J. Musliner, E. H. Durfee, and K. G. Shin,
<!WA18><a HREF="http://www.cs.umd.edu/users/musliner/papers/tsmc.ps">
CIRCA: A Cooperative Intelligent Real-Time Control Architecture</a>
<i>IEEE Transactions on Systems, Man, and Cybernetics</i>, Vol 23 #6, 1993. </a>
<p>

D. J. Musliner, 
<!WA19><a HREF="http://www.cs.umd.edu/users/musliner/papers/musliner-diss.ps">
CIRCA: The Cooperative Intelligent Real-Time Control Architecture</a>
<i>Ph.D. Thesis</i>, The University of Michigan, Ann Arbor, MI, 1993. </a>
<p>

D. J. Musliner, E. H. Durfee, and K. G. Shin,
<!WA20><a HREF="http://www.cs.umd.edu/users/musliner/papers/musliner-sigman.ps"> 
Integrating Intelligence and Real-Time Control into Manufacturing Systems</a>,
<i>Working Notes of the SIGMAN Workshop on Intelligent
Manufacturing Technology</i>, July 1993.
<p>


D. J. Musliner, E. H. Durfee, and K. G. Shin,
<!WA21><a HREF="http://www.cs.umd.edu/users/musliner/papers/musliner-rtoss.ps"> 
Any-Dimension Algorithms
</a>,
in <i>Proc. Workshop on Real-Time Operating Systems and Software</i>, May 1992.
<p>

D. J. Musliner, E. H. Durfee, and K. G. Shin,
<!WA22><a HREF="http://www.cs.umd.edu/users/musliner/papers/musliner-ss92.ps"> 
Reasoning About Bounded Reactivity to Achieve Real-Time Guarantees</a>, in
<i> Proc. AAAI Spring Symposium on Selective Perception</i>, March 1992.
<p>

D. J. Musliner, E. H. Durfee, and K. G. Shin,
<!WA23><a HREF="http://www.cs.umd.edu/users/musliner/papers/caia91.ps"> 
Execution Monitoring and Recovery Planning with Time</a>, in
<i> Proc. Conf. on Artificial Intelligence
  Applications</i>, February 1991.
<p>

Edmund H. Durfee and Victor R. Lesser. Incremental Planning to 
Control a Time-Constrained, Blackboard-Based Problem Solver. <I>IEEE 
Transactions on Aerospace and Electronic Systems</I>, special issue on 
space telerobotics, 24(5):647-662, September 1988.<p>

Victor R. Lesser, Jasmina Pavlin, and Edmund H. Durfee. Approximate 
Processing in Real-Time Problem Solving. <I>AI Magazine</I>, Vol. 9, No. 1, 
pages 49--61, Spring 1988.<p>

Edmund H. Durfee. Towards Intelligent Real-Time Cooperative Systems. 
In   <I>AAAI Spring Symposium on Planning in Uncertain, Unpredictable, or 
Changing Environments</I> , pages 29--33, Stanford, CA, March 1990.<p>



<H2>Short Description</H2>

As Artificial Intelligence (AI) techniques become mature, there has been
growing interest in applying these techniques to controlling complex
real-world systems which involve hard deadlines.  In such systems, the
controller is required to respond to certain inputs within rigid
deadlines, or the system may fail catastrophically.  For example, the
Mars Rover project requires a partially- or fully-autonomous vehicle
that can perform unsupervised navigation in hazardous conditions, where
errors could mean the loss of multi-million dollar research and
development efforts.  Controlling the Rover includes real-time tasks
such as obstacle avoidance and emergency reactions to unexpected terrain
hazards.  If the system ever fails to meet the deadlines associated with
these control tasks, it may suffer damage tantamount to mission failure.
Since the number of possible domain situations is too large to be fully
enumerated, and the consequences of failure are so severe, testing alone
is insufficient to guarantee the required real-time performance.  These
control problems require systems which can be proven to meet the
hard deadlines which the environment imposes. <p>

Hard-wired control schemes using fixed algorithms are amenable to such
performance analysis, but cannot address high-level problems such as
reasoning about goals, resource restrictions, and recovery from
unexpected failures.  Unfortunately, many of the AI techniques and
heuristics developed to solve these high-level problems are not suited
to analyses that would provide guaranteed response times.  For example,
systems that learn are able to form new chains of inferences, resulting
in changing performance characteristics that may defy worst-case
bounding.  Even when AI techniques can be shown to have predictable
response times, the variance in these response times is typically so
large that providing timeliness guarantees based on the worst-case
performance would result in severe underutilization of the computational
resources during normal operations. <p>

Thus we perceive an apparent conflict between the nature of AI and the
needs of real-world, real-time control systems.  While AI methods are
characterized by unpredictable or high-variance performance, real-time
control systems require constant, predictable performance.  Most
research on ``real-time AI'' (RTAI) focuses either on restricted AI
techniques that have predictable performance characteristics or on
reactive systems that retain little of the power of traditional AI. <p>

The AI Lab and the Real-Time Computing Lab are cooperating on a
new branch of RTAI research here at the University of Michigan.  To
combine unrestricted AI techniques with the ability to make hard
performance guarantees, we are investigating a Cooperative Intelligent
Real-Time Control Architecture (CIRCA).  In this architecture, an AI
subsystem reasons about task-level problems that require its powerful
but unpredictable reasoning methods, while a separate real-time
subsystem uses its predictable performance characteristics to deal with
control-level problems that require guaranteed response times.  The key
difficulty with this approach is allowing the subsystems to interact
without compromising their respective performance goals.  We have
developed a scheduling module and a structured interface that allow the
unconstrained AI subsystem to asynchronously direct the real-time
subsystem without violating any response-time guarantees. <p>

Realistic intelligent control systems must recognize their resource
limitations and make tradeoffs in the quality of their control outputs,
or responses.  Many systems recognize resource limitations and trade off
the precision, confidence, or timeliness of their responses.  CIRCA
extends this mechanism by allowing the system to explicitly trade off
the completeness of its responses.  CIRCA's AI subsystem and scheduler
cooperatively reason about the real-time subsystem's execution
resources, and choose a subset of responses that the real-time
subsystem will guarantee.  By manipulating the responses that the
real-time subsystem is guaranteeing, the AI subsystem attempts to ensure
that the real-time subsystem will meet hard deadlines and also achieve
the overall system goals.  CIRCA also provides mechanisms to utilize the
time which becomes available when guaranteed mechanisms use less than
their worst-case scheduled time allowance. <p>

To achieve flexible control, CIRCA requires that the AI methods reason
about the expected real-time demands of the environment and build
control plans to guarantee meeting those demands.  CIRCA does this using
a formal graph-based model of agent/environment interactions, exploring
a space of states that the system could be in due to its own actions,
due to external events, and due to the passage of time.  In constructing
control plans, CIRCA determines what actions it must guarantee to take
and how often it will be able to take them to ensure that the system
does not enter a state where it could transition into failure (due to
the passage of time).  Currently, CIRCA is able to develop such control
plans when possible, and when not possible CIRCA provides well-defined
transformations to the graph model (based predominantly on eliminating
or extending various types of transitions) that allow it to
systematically relax requirements until it can guarantee the performance
of a control plan.  Our ongoing work is investigating how to choose from
among candidate transformations to yield the best possible control plan.
We are also investigating improved scheduling techniques for efficiently
generating guaranteed control plans, using internal state in the
real-time subsystem to reduce costly sensory actions, and strategies for
transitioning among control plans.  Application domains for CIRCA
include manufacturing process control and mobile robotics. <p>

</BODY>

<HR><ADDRESS>
<B>Last Updated: </B><I>5/4/95</I>
</ADDRESS>
